#pragma once
#include<iostream>
#include<string>
#include<bitset>
using namespace std;

//仿函数
struct BKDRHash 
{
	size_t operator()(const string& key)
	{
		//BKDR
		size_t hash = 0;
		for (auto e : key)
		{
			hash *= 31;
			hash += e;
		}
		return hash;
	}
};

struct APHash
{
	size_t operator()(const string& key)
	{//AP	//异或
		size_t hash = 0;
		for (size_t i = 0; i<key.size(); i++)
		{
			char ch = key[i];
			if ((i & 1) == 0)
			{
				hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
			}
			else
			{
				hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
			}
		}
		return hash;
	}
};

struct DJBHash
{
	size_t operator()(const string& key)
	{//DJB	//移位

		size_t hash = 5381;
		for (auto ch : key)
		{
			hash += (hash << 5) + ch;
		}
		return hash;
	}
};


template<size_t N, 
	class K = string, 
	class HashFunc1 = BKDRHash,
	class HashFunc2 = APHash,
	class HashFunc3 = DJBHash>
class BloomFilter
{
public:
	//插入
	void Set(const K& key)
	{//三个位置判断在不在
		size_t hash1 = HashFunc1()(key) % N;
		size_t hash2 = HashFunc2()(key) % N;
		size_t hash3 = HashFunc3()(key) % N;

		_bs.set(hash1);
		_bs.set(hash2);
		_bs.set(hash3);

	}

	//一般不支持删除
	//用引用计数，即多个位标记一个值，多个位存计数
	//但是这样的话，空间消耗就变大了，没意义了

	//判断在不在
	bool Test(const K& key)
	{
		size_t hash1 = HashFunc1()(key) % N;
		if (_bs.test(hash1) == false)
		{//判断不在，是准确的
			return false;
		}

		size_t hash2 = HashFunc2()(key) % N;
		if (_bs.test(hash2) == false)
		{
			return false;
		}

		size_t hash3 = HashFunc3()(key) % N;
		if (_bs.test(hash3) == false)
		{
			return false;
		}

		//判断在，存在误判
		return true;
	}
private:
	bitset<N> _bs;
};